package me.timlong;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class WordBreak {
    /**
     * 给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。
     * 例如:
     * 给定s = “leetcode”；
     * dict=["leet", "code"].
     * 返回true，因为"leetcode"可以被分割成"leet code".
     *
     * 这里定义递推式
     * f[i] -> denotes that weather the substring s[0, ..., i-1] participle
     *
     *
     * @param
     */
    public boolean wordBreak(String s, Set<String> dict) {
        int len = s.length();
        boolean[] array = new boolean[len + 1];
        array[0] = true;

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if(array[j] && dict.contains(s.substring(j, i))){
                    array[i] = true;
                    break;
                }
            }
        }
        return array[len];
    }

    public static void main(String[] args) {
        String s = "leetcode";
        String[] dictArr = {"leet", "code"};
        HashSet<String> dict = new HashSet<String>(Arrays.asList(dictArr));

        System.out.println(new WordBreak().wordBreak(s, dict));

    }


}
